import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: GodK
 * Date: 2024-04-12
 * Time: 20:42
 */
//最小的k个数
class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Main {
    public static void main(String[] args) {
        int arr[] = {1,3,5,7,2,4,6,8};
        smallestK(arr,4);
    }
    public static int[] smallestK1(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        int[] ret = new int[k];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = minHeap.poll();
        }

        return ret;
    }

    public static int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k == 0)return ret;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());
        for(int i = 0;i < k ; i++){
            maxHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int val = maxHeap.peek();
            if(val > arr[i]) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }
    static void TestPriorityQueue() {
        int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};

        // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
        // 否则在插入时需要不多的扩容
        // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        for (int e : arr) {
            q.offer(e);
        }

        System.out.println(q.size());  // 打印优先级队列中有效元素个数
        System.out.println(q.peek());  // 获取优先级最高的元素

        // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
        q.poll();
        q.poll();
        System.out.println(q.size());  // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素

        q.offer(0);
        System.out.println(q.peek());  // 获取优先级最高的元素

        // 将优先级队列中的有效元素删除掉，检测其是否为空
        q.clear();
        if (q.isEmpty()) {
            System.out.println("优先级队列已经为空!!!");
        } else {
            System.out.println("优先级队列已经不为为空!!!");
        }
    }
}
